//============================================================================
// Name        : GSP295_Wk4_HashTable
// Author      : Ronald Ram
// Version     :
// Copyright   : GSP295 Wk4 Program - Hash Tables
// Description : Hash Table Implemented as Array in C++
//============================================================================


#include "Graph.h"
#include <stack>
//using namespace std;


namespace GSP295_Wk5
{
	//C001: DEFAULT CONSTRUCTOR
	Graph::Graph()
	{
		
		vertexList = new Vertex[MAX_VERTS];
		this->adjMatrix = new int*[MAX_VERTS];

		this->size = 0;
		Init();
	}

	//C003: Init Method
	void Graph::Init()
	{
		const int ZERO = 0;

		//Initialize Vertex List
		for (int i=0; i< MAX_VERTS; ++i) 
		{
			this->vertexList[i].data = "NULL";
			this->vertexList[i].wasVisited = false;
		}

		//Initialize Adjacency Matrix
		for (int i=ZERO; i< MAX_VERTS; ++i) 
		{
			this->adjMatrix[i] = new int[MAX_VERTS];

			for (int j=ZERO; j< MAX_VERTS; ++j) 
			{
				this->adjMatrix[i][j] = -1;
			}
		}
	}

	//C002: DESTRUCTOR
	Graph::~Graph()
	{
		this->size = NULL;
		delete [] vertexList;

		//Delete 2D array
		for (int i=0; i< MAX_VERTS; ++i) { delete [] adjMatrix[i]; }
		delete [] adjMatrix;
	}

	//M001: Reset the Graph
	void Graph::MakeEmpty()
	{
		this->size = 0;
		Init();
	}

	//M002: Check if Graph is EMPTY
	bool Graph::isEmpty() const
	{
		return ( this->size == 0 );
	}

	//M003: Check if Graph is FULL
	bool Graph::isFull() const
	{
		return ( this->size == MAX_VERTS );
	}

	//M004: Add a vertex to Graph
	//Rule: ONLY unique Vertices are added to 'vertexList'
	bool Graph::AddVertex( Vertex vertex )
	{
		bool hasCollided = false;

		//Check if 'vertexList' isFull
		if ( !isFull() )
		{
			//COLLISION CHECK: if input vertex already exists in 'vertexList'
			for (int i=0; i< this->size; ++i)
			{
				if ( this->vertexList[i].data == vertex.data ) 
				{
					hasCollided = true;
					break;
				}
			}

			//Add Vertex to array if NO Collision
			if ( !hasCollided ) 
			{
				this->vertexList[this->size].data = vertex.data;
				this->vertexList[this->size].wasVisited = vertex.wasVisited;
				++ this->size;
			}
		} 
		
		return hasCollided;
	}

	//M005: Add an Edge w/ its weight between two Vertices
	bool Graph::AddEdge( Vertex fromVtx, Vertex toVtx, int weight )
	{
		bool found = false;
		int row = -1, col = -1;

		//Search Adjacency Matrix - ROW 
		for (int i=0; i< this->size; ++i) 
		{
			if ( this->vertexList[i].data == fromVtx.data ) 
			{ 
				row = i; //found matching row

				//Search Adjacency Matrix - COLUMN
				for (int j=0; j< this->size; ++j) 
				{
					if ( this->vertexList[j].data == toVtx.data ) 
					{
						col = j; //found matching column
						found = true;
						break;
					}
				}//inner for-loop
			}
		}//outer for-loop

		//Add Edge to Adjacency Matrix, if Vertices are found
		if ( found ) 
		{ 
			adjMatrix[row][col] = weight; 
		}

		return found;
	}

	//M006: Returns the Weight Value b/w 2 Vertices
	int Graph::WeightIs( Vertex fromVertex, Vertex toVertex )
	{
		bool found = false;
		int row = -1, col = -1; 
		int weight = -1; //Value: -1 means Vertices not found

		//Search Adjacency Matrix - ROW 
		for (int i=0; i< this->size; ++i) 
		{
			if ( this->vertexList[i].data == fromVertex.data ) 
			{ 
				row = i; //found matching row

				//Search Adjacency Matrix - COLUMN
				for (int j=0; j< this->size; ++j) 
				{
					if ( this->vertexList[j].data == toVertex.data ) 
					{
						col = j; //found matching column
						found = true;
						break;

					}
				}//inner for-loop
			}
		}//outer for-loop

		//Return Edge Weight from Adjacency Matrix, if Vertices are found
		if ( found ) 
		{ 
			weight = adjMatrix[row][col]; 
		}

		return weight;
	}

	
	//M007: Returns an array of Vertices that are adjacent to vertex
	//Post: Method prints E(graph) combo of Vertices if there are any matches found
	void Graph::GetToVertices( Vertex vertex )
	{
		bool found = false;
		int row = -1, counter = 0;
		
		for (int i=0; i< this->size; ++i) 
		{
			if ( this->vertexList[i].data == vertex.data ) 
			{
				row = i; //Found root Vertex
				found = true;
				break;
			}
		}//for-loop

		string *vList = new string[this->size];

		if ( found ) 
		{
			
			for (int i=0; i< this->size; ++i) 
			{
				if ( this->adjMatrix[row][i] >= 0 ) 
				{
					vList[counter] = vertexList[i].data;
					++counter;
				}
			}//for-loop

			if ( counter !=0 ) 
			{
				cout << "\n\n-----------------Vertex List E(Graph)-----------------\n" << endl;
				cout << "\Adjacent Vertices found\n" << endl;

				for (int i=0; i< counter; ++i) 
				{
					cout << "Vertices: " <<  vertex.data << " --> " << vList[i] << endl;
				}

				cout << "\n\n-----------------Vertex List E(Graph)-----------------\n\n\n" << endl;
			}
			else
			{
				cout << "\n\nNo Adjacent Vertices found near " << vertex.data << "\n\n" << endl;
			}
		}
		else
		{
			cout << "\n\nNo Adjacent Vertices found near " << vertex.data << "\n\n" << endl;
		}
	}

	//M008: //M008: Find the DFS Path between 2 Vertices
	//Pre: Methods takes 2 Vertices as input
	//Post Method Prints out the path, if any found
	void Graph::DFS( Vertex fromVtx, Vertex toVtx )
	{
		if ( VertexExists(fromVtx) && VertexExists(toVtx) ) 
		{
			int counter = 0;
			Vertex temp, *theStack = new Vertex[this->size];
			
			theStack[counter] = vertexList[getVertexIndex(fromVtx)];
			++counter;
			vertexList[getVertexIndex(fromVtx)].SetWasVisited(true); //mark as visited

			while ( counter !=0 ) //until Stack empty
			{
				int v = getAdjVertex_UnVisited( getVertexIndex(fromVtx) );

				if ( v == -1 ) 
				{
					--counter;
					theStack[counter].Assign("NULL", false); //if no adj Vertex, pop a new one
				} 
				else 
				{
					vertexList[v].SetWasVisited(true);
					theStack[counter] = vertexList[v];
					++counter;
				}
			}//end while

			if ( counter != 0 ) 
			{
				//Print the stack
				cout << "\n\n-----------------Vertex List-----------------" << endl;
				cout << "Print out of Path. From: " << fromVtx.data << ", To: " << toVtx.data << "\n\n" << endl;
				cout << "START --> ";
				for (int i=0; i< counter; ++i )
				{
					cout << theStack[i].data << " --> ";
				}
				cout << "END";
				cout << "\n\n-----------------Vertex List-----------------" << endl;

				//Reset hasVisited for all Vertices
				for (int i=0; i< this->size; ++i )
				{
					vertexList[i].SetWasVisited(false);
				}
			} 
			else { cout << "\n\nNo Match for Vertices, cannot find Path\n\n" << endl;
			}
		} 
		else 
		{
			cout << "\n\nNo Match for Vertices, cannot find Path\n\n" << endl;
		}
	}


	//M009: Find if Vertex is in Graph
	bool Graph::VertexExists( Vertex v )
	{
		bool found = false;

		for (int i=0; i< this->size; ++i)
		{
			if ( this->vertexList[i].data == v.data ) 
			{
				found = true;
				break;
			}
		}

		return found;
	}

	//M010: Return the Index of the Vertex in the graph
	int Graph::getVertexIndex( Vertex v )
	{
		int index;

		for (int i=0; i< this->size; ++i)
		{
			if ( this->vertexList[i].data == v.data ) 
			{
				index = i;
				break;
			}
		}

		return index;
	}

	//M011: return Index to next adj vertex in the graph
	int Graph::getAdjVertex_UnVisited( int index )
	{
		int indexLocal = -1;

		for (int i=0; i< this->size; ++i)
		{
			if ( this->adjMatrix[index][i] >= 0 && vertexList[i].wasVisited == false ) 
			{
				indexLocal = i; //return first adj unvisited vertex index
				break;
			}
		}
		return indexLocal;
	}


	//
	
	/************************************************************************/
	/*                                                                      */
	/************************************************************************/
	void Graph::Print()
	{
		cout << "\n\n-----------------Vertex List-----------------" << endl;
		for (int i=0; i< this->size; ++i) 
		{
			cout << "Index[" << i<< "] = " << vertexList[i].data << ", " << vertexList[i].wasVisited << endl;
		}
		cout << "\n\n-----------------Vertex List-----------------" << endl;


		cout << "\n\n\n\n-----------------Adjacency Matrix-----------------" << endl;
		for (int i=0; i< this->size; ++i) 
		{
			for (int j=0; j< this->size; ++j) 
			{
				cout << "Index[" << i << "][" << j << "] = " << this->adjMatrix[i][j] << endl;;
			}
			cout << endl;
		}
		cout << "\n\n-----------------Adjacency Matrix-----------------" << endl;
	}
}//namespace
